/*
28. 找出字符串中第一个匹配项的下标
. 简单
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
*/

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class Solution {//使用KMP算法求解
public:
    vector<int> get_next_arry(string str)//求next数组
    {
        vector<int> next;
        if(str.size()==1)
        {
            next.push_back(0);
        }
        else if(str.size()==2)
        {
            next.push_back(0);
            next.push_back(0);
        }
        else
        {
            next.push_back(0);
            next.push_back(0);
            auto left = str.begin();
            auto right_const = left + 1;
             
            int value = 0;
            while(right_const!=str.end()-1)
            {
                auto right = right_const;
                if(*left==*right)
                {
                    value++;
                    next.push_back(value);
                    left++;
                }
                else
                {
                    left = str.begin();
                    right = right - (value - 1);
                    value--;
                }

                right_const++;
            }
        }
        return next;
    }
    void print_next_arry(vector<int> next)
    {
        for(int n:next)
        {
            cout << n << " " << endl;
        }
    }
    int strStr(string haystack, string needle) //重点在于量个比较指针的位置变化
    {
        auto faster_const = haystack.begin();
        auto lower_const = needle.begin();
        vector<int> next = get_next_arry(needle);
        while(faster_const!=haystack.end())
        {
            if(*faster_const==*lower_const)
            {
                faster_const++;
                lower_const++;
                if(lower_const==needle.end())
                    return faster_const - haystack.begin() - needle.size();
            }
            else{
                if(lower_const==needle.begin())
                {
                    faster_const++;
                }
                int n = next[lower_const - needle.begin()];
                lower_const = needle.begin() + n;
            }
            
        }
        return -1;
    }
};

int main()
{
    Solution soul;
    string s1 = "aabaaabaaac";
    string s2 = "aabaaac";
    int res=soul.strStr(s1,s2);
    cout << res;
    vector<int> next=soul.get_next_arry(s2);
    // soul.print_next_arry(next);
    return 0;
}

//暴力求解
// class Solution {
// public:
//     int strStr(string haystack, string needle) 
//     {
//         auto faster_const = haystack.begin();
//         auto lower_const = needle.begin();
//         while(faster_const!=haystack.end())
//         {
//             if(*faster_const==*lower_const)
//             {
//                 auto faster = faster_const;
//                 auto lower = lower_const;
//                 while(*faster==*lower)
//                 {
//                     faster++;
//                     lower++;
//                     if(lower==needle.end())
//                         return faster_const - haystack.begin();
//                 }
//             }
//             faster_const++;
//         }
//         return -1;
//     }
// };